#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

import random
import time

DefaultMax = -9999999

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start, self.end = start, end
        self.left, self.right = None, None
        self.max = DefaultMax

class SegmentTree:
    def __init__(self, nums):
        self.nums = nums
        self.len = len(self.nums)

        self.root = self.build()

    def build(self):
        # [start, end]  , 闭区间
        return self.rec_build(0, self.len)[0]

    def rec_build(self, start, end):
        # [start, end), 开闭区间
        node = SegmentTreeNode(start, end)
        if end - start == 1:
            node.max = self.nums[start]
            return node, node.max

        mid = (start + end) // 2

        left_node, left_max  = self.rec_build(start, mid)
        right_node, right_max = self.rec_build(mid, end)

        node.left, node.right = left_node, right_node
        node.max = max(left_max, right_max)
        return node, node.max

    def less_then(self, idx):
        # 在>idx的num中, 比self.nums[idx]小的有多少个 (逆序数个数)
        return self.less_then_rec(idx, self.root)

    def less_then_rec(self, idx, node):
        # [start, end), 开闭
        if node == None:
            return 0

        start, end = node.start, node.end
        if idx >= end:
            return 0

        the_num = self.nums[idx]
        if the_num > node.max:
            # HINT: 线段树的优势所在, 整片区域判断
            return end - start

        return self.less_then_rec(idx, node.left) + self.less_then_rec(idx, node.right)

def reverse_order(nums):
    # NOTE: 对于逆序情况, 线段树算的相当的快! 因为总能碰到 the_num > node.max的情况(导致不用再深入到树的内部去)
    start = time.time()
    tree = SegmentTree(nums)
    print("tree ok")
    l = len(nums)
    cnt = 0
    for idx in range(l-1):
        # cnt += tree.less_then(idx)
        result = tree.less_then(idx)
        cnt += result

    print("1 span ", time.time() - start)
    return cnt

def reverse_order2(nums):
    start = time.time()

    cnt = 0
    l = len(nums)

    for first_idx in range(l-1):
        for second_idx in range(first_idx+1, l):
            if nums[second_idx] < nums[first_idx]:
                cnt += 1

    print("2 span ", time.time() - start)
    return cnt

def test():
    assert reverse_order([5, 4, 3, 2, 1]) == 10
    assert reverse_order([2, 4, 3, 1]) == 4

    # n = 1000000
    n = 10000
    l = list(range(n, 0, -1))
    # random.shuffle(l)

    # assert reverse_order( range(n, 0, -1) ) == n*(n-1)//2
    # assert reverse_order( l ) == n*(n-1)//2
    assert reverse_order( l ) == reverse_order2(l)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
